package tree.leetcode_105_medium;

public class BuildTree {
    public static void main(String[] args) {
        int[] pre = {3, 9, 20, 15, 7};
        int[] in = {9, 3, 15, 20, 7};
        buildTree(pre, in);
    }

    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        //使用左闭右闭区间
        return buildHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public static TreeNode buildHelper(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        //递归终止条件，当前节点无左或者无右
        if (preStart > preEnd || inStart > inEnd) {
            return null;
        }
        //先序遍历中，第一个节点就是整棵树的根节点。
        int rootValue = pre[preStart];
        TreeNode root = new TreeNode(rootValue);

        //寻找中序遍历的根节点所在位置
        int inRootIndex = 0;
        //遍历中序遍历结果的过程
        for (int i = inStart; i <= inEnd; i++) {
            if (in[i] == rootValue) {
                inRootIndex = i;
                break;
            }
        }
        //中序遍历中，根节点左边的节点都是左子树，根节点右边的都是右子树，记录一下左子树有多个节点。
        int leftNums = inRootIndex - inStart;

        //构造左子树，先序遍历中，根节点后的leftNums个节点都是左子树。    中序遍历中，从start到根节点前一个节点都是左子树
        root.left = buildHelper(pre, preStart + 1, preStart + leftNums, in, inStart, inRootIndex - 1);

        //构造右子树，先序遍历中，根节点后的leftNums个节点都是左子树，再往后都是右子树，所以 + 1
        //中序遍历中，根节点(inRootIndex)后面都是右子树。
        root.right = buildHelper(pre, preStart + leftNums + 1, preEnd, in, inRootIndex + 1, inEnd);
        return root;
    }
}
